//
// Created by francklinson on 2021/7/11 AT 20:05.
//

//这里有一个非负整数数组arr，你最开始位于该数组的起始下标start处。当你位于下标i处时，你可以跳到i + arr[i] 或者 i - arr[i]。
//
//请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
//
//注意，不管是什么情况下，你都无法跳到数组之外。
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * 判断是否有一条路径碰到0
     * @param arr
     * @param start
     * @return
     */
    bool canReach(vector<int> &arr, int start) {
        if (arr[start]==0) return true;
        queue<int> q;
        vector<bool> seen(arr.size(), false);
        q.push(start);
        seen[start] = true;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (arr[p] == 0) return true;
            for (auto &nextVal:vector<int>{p + arr[p], p - arr[p]}) {
                if (nextVal >= 0 and nextVal < arr.size() and not seen[nextVal]) {
                    if (arr[nextVal] == 0) return true;    /// 遇到0
                    q.push(nextVal);
                    seen[nextVal] = true;
                }
            }
        }
        return false;
    }
};

int main() {
    vector<int> arr{4, 2, 3, 0, 3, 1, 2};
    Solution solution;
    cout << solution.canReach(arr, 5);
    return 0;
}
